# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/7 13:49 
"""
"""
链接：https://blog.csdn.net/github_39560448/article/details/117190753
对撞指针是双指针算法之一
对撞指针从两端向中间迭代数组，一个指针从始端开始，另一个从末端开始
对撞指针的终止条件是两个指针相遇
对撞指针常用于排序数据


"""

"""
两数之和，输入一个有序数组，
例：【2，7，11，15】，target=9

"""


# ==================有序
def two_num_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] + nums[right] == target:
            return [left, right]
        else:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                left += 1
        print(left, right, nums[left], nums[right])
    if left >= right:
        return False
    else:
        return [left, right]


# =====================无序
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        sorted_id = sorted(range(len(nums)), key=lambda k: nums[k])
        head = 0
        tail = len(nums) - 1
        sum_result = nums[sorted_id[head]] + nums[sorted_id[tail]]
        while sum_result != target:
            if sum_result > target:
                tail -= 1
            elif sum_result < target:
                head += 1
            sum_result = nums[sorted_id[head]] + nums[sorted_id[tail]]
        return [sorted_id[head], sorted_id[tail]]


class Solution2:
    def two_sum(self, nums, target):
        """
        计算两数之和
        """
        sorted_id = sorted(range(len(nums)), key=lambda x: nums[x])
        left, right = 0, len(nums) - 1
        sum_resutl = nums[sorted_id[left]] + nums[sorted_id[right]]
        while sum_resutl != target:
            if sum_resutl > target:
                right -= 1
            else:
                left += 1
            sum_resutl = nums[sorted_id[left]] + nums[sorted_id[right]]
        return [sorted_id[left], sorted_id[right]]


class Solution3:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        for index, num in enumerate(nums):
            another_num = target - num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
            print(hashmap)
        return None



"""
有符回文数：



"""


def palindrome_num(num):
    sign = 1 if num > 0 else -1  # 判断符号
    num_str = list(str(abs(num)))
    num_str2 = num_str.copy()
    left, right = 0, len(num_str) - 1
    print(f'num_str={num_str},num_str2={num_str2}')
    while left < right:
        num_str[left], num_str[right] = num_str[right], num_str[left]
        left += 1
        right -= 1
        print(f'left={left},right={right},num_str2={num_str2}')
    if "".join(num_str2) == "".join(num_str):
        if sign == 1:
            return True
        else:
            return False
    else:
        return False


"""
反转正整数
"""


def reverse_integer2(num):
    if num < -(1 << 31 - 1) or num > (1 << 31) - 1:
        print('溢出')
        return 0
    sign = 1 if num > 0 else -1  # 判断符号
    num_str = list(str(abs(num)))
    num_str2 = num_str.copy()
    left, right = 0, len(num_str) - 1
    print(f'num_str={num_str},num_str2={num_str2}')
    while left < right:
        num_str[left], num_str[right] = num_str[right], num_str[left]
        left += 1
        right -= 1
        print(f'left={left},right={right},num_str2={num_str2}')
    return sign * int("".join(num_str))


"""

包含更多的水，例：a=[1,8,6,2,5,4,8,3,7]
output:49
"""


def container_with_water(a):
    left, right = 0, len(a) - 1
    max_res = 0
    while left < right:
        width = right - left
        high = 0
        if a[left] < a[right]:
            # 容器是否能取足够多的水，高度为两个数中最小的
            high = a[left]
            left += 1
        else:
            high = a[right]
            right -= 1
        temp = width * high
        if temp > max_res:
            max_res = temp
    return max_res


"""
二进制数反转
"""


def reverseBits(a):
    A = list(a)
    left, right = 0, len(a) - 1
    while left < right:
        A[left], A[right] = A[right], A[left]
        left += 1
        right -= 1
    AA = "".join(A)
    return AA